#pragma once
#include<iostream>
using namespace std;

template<class K>
struct BStreeNode
{
	BStreeNode(const K& key)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{

	}

	K _key;
	BStreeNode<K>* _left;
	BStreeNode<K>* _right;

};

template<class K>
class BSTree
{
	typedef BStreeNode<K> Node;
public:
	bool insert(const K& key)
	{

		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		else
		{
			Node* PrevNode = nullptr;
			Node* CurNode = _root;
			while (CurNode)
			{
				if (CurNode->_key < key)
				{
					PrevNode = CurNode;
					CurNode = CurNode->_right;
				}
				else if (CurNode->_key > key)
				{
					PrevNode = CurNode;
					CurNode = CurNode->_left;
				}
				else
				{
					return false;
				}
			}

			CurNode = new Node(key);
			if (PrevNode->_key < key)
			{
				PrevNode->_right = CurNode;
			}
			else if (PrevNode->_key > key)
			{
				PrevNode->_left = CurNode;
			}

			return true;
		}
	}

	bool Find(const K& key)
	{
		Node* CurNode = _root;

		while (CurNode)
		{
			if (key < CurNode->_key)
			{
				CurNode = CurNode->_left;
			}
			else if (key > CurNode->_key)
			{
				CurNode = CurNode->_right;
			}
			else
			{
				return true;
			}
		}

		return false;
	}

	bool Erase(const K& key)
	{
		Node* PrevNode = nullptr;
		Node* CurNode = _root;
		while (CurNode)
		{
			if (key < CurNode->_key)
			{
				PrevNode = CurNode;
				CurNode = CurNode->_left;
			}
			else if (key > CurNode->_key)
			{
				PrevNode = CurNode;
				CurNode = CurNode->_right;
			}
			else
			{
				if (CurNode->_left == nullptr)
				{
					if (PrevNode == nullptr)
					{
						_root = CurNode->_right;
						return true;
					}

					if (PrevNode->_left == CurNode)
					{
						PrevNode->_left = CurNode->_right;
					}
					else if (PrevNode->_right == CurNode)
					{
						PrevNode->_right = CurNode->_right;
					}

					delete CurNode;
					return true;
				}
				else if(CurNode->_right == nullptr)
				{
					if (PrevNode == nullptr)
					{
						_root = CurNode->_left;
						return true;
					}

					if (PrevNode->_left == CurNode)
					{
						PrevNode->_left = CurNode->_left;
					}
					else if (PrevNode->_right == CurNode)
					{
						PrevNode->_right = CurNode->_left;
					}

					delete CurNode;
					return true;
				}
				else
				{
					Node* Prev = CurNode;
					Node* RightMin = CurNode->_right;
					while (RightMin->_left)
					{
						Prev = RightMin;
						RightMin = RightMin->_left;
					}

					CurNode->_key = RightMin->_key;
					
					if (Prev->_left == RightMin)
						Prev->_left = RightMin->_right;
					else
						Prev->_right = RightMin->_right;

					delete RightMin;
					return true;
				}
			}
			
		}
		return false;
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

	void _Inorder(Node*root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << root->_key << " ";
		_Inorder(root->_right);
		
	}
private:
	Node* _root=nullptr;
};
